package com.hy.study.tree;

/**
 * 线索化二叉树
 */
public class ThreadBinaryTreeDemo {
    public static void main(String[] args) {
        Node root = new Node(1, "tom");
        Node node2 = new Node(3, "jack");
        Node node3 = new Node(6, "smith");
        Node node4 = new Node(8, "mary");
        Node node5 = new Node(10, "king");
        Node node6 = new Node(14, "dim");
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        //线索化
        ThreadBinaryTree binaryTree = new ThreadBinaryTree(root);
        //测试 10号节点
        // binaryTree.threadedNodes();
        binaryTree.threadedPreNode();
        Node leftNode = node5.getLeft();
        Node rightNode = node5.getRight();
        System.out.println("10号节点的前驱节点是:" + leftNode);
        System.out.println("10号节点的后继节点是:" + rightNode);
        System.out.println("--------使用线索化遍历-----");
       // binaryTree.threadList();
        binaryTree.threadedListPre();


    }

}

class ThreadBinaryTree {
    private Node root;
    //为了实现线索化，需要创建要给指向前节点的前驱节点的指针
    //在递归进行线索化时，pre 总是保留前一个节点。
    private Node pef;

    public ThreadBinaryTree(Node root) {
        this.root = root;
    }

    public void threadedNodes() {
        this.threadedNodes(root);
    }

    /**
     * 对二叉树进行中序线索化的方法
     *
     * @param node
     */
    public void threadedNodes(Node node) {
        if (node == null) {
            System.out.println("该节点为空,无法进行线索化");
            return;
        }
        //1.先线索化左子树
        threadedNodes(node.getLeft());
        //2.线索化当前节点
        //2.1处理当前节点的前驱节点
        if (node.getLeft() == null) {
            //让当前节点的左指针指向前驱节点
            node.setLeft(pef);
            node.setLeftTyep(1);
        }
        //处理后续节点
        //2.2让前驱节点的右指针指向当前节点
        if (pef != null && pef.getRight() == null) {
            pef.setRight(node);
            pef.setRightType(1);
        }
        //3.每处理一个节点之后，让当前节点是下一个节点
        pef = node;
        //4.线索化右子树
        threadedNodes(node.getRight());

    }

    public  void threadedPreNode(){
        this.threadedPreNode(root);
    }
    /**
     * 对二叉树前序线索化
     * @param node 根节点
     */
    public void threadedPreNode(Node node){
        if(node==null){
            System.out.println("节点为空，无法进行前序线索化");
            return;
        }
        //1.线索化 当前节点
      //  1.1 处理当前节点的前驱节点
        if(node.getLeft()==null){
            node.setLeft(pef);
            node.setLeftTyep(1);
        }
        //1.2处理右节点
        if(pef!=null && pef.getRight()==null){
            pef.setRight(node);
            pef.setRightType(1);
        }
        pef=node;

        //2.线索化左子树
        threadedPreNode(node.getLeft());
        //3.线索化右子树
        threadedPreNode(node.getRight());


    }
    /**
     * 二叉树 开始前序遍历
     */
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空无法遍历");
        }
    }

    /**
     * 二叉树 中序遍历
     */
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空无法遍历");
        }
    }

    /**
     * 二叉树 后续遍历
     */
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空无法遍历");
        }
    }

    /**
     * 前序遍历
     *
     * @param no
     * @return
     */
    public Node preOrderSearch(int no) {
        if (root != null) {
            return root.preSearch(no);
        } else {
            return null;
        }

    }

    /**
     * 中序遍历
     *
     * @param no
     * @return
     */
    public Node infixOrderSearch(int no) {
        if (root != null) {
            return root.infixSearch(no);
        } else {
            return null;
        }
    }

    /**
     * 后序遍历
     *
     * @param no
     * @return
     */
    public Node postOrderSearch(int no) {
        if (root != null) {
            return root.postSearch(no);
        } else {
            return null;
        }
    }

    /**
     * 删除节点
     */
    public void delete(int id) {
        if (root != null) {
            if (root.getId() == id) {//如果root 就是需要删除的
                root = null;
            } else {
                root.delete(id);
            }
        } else {
            System.out.println("空树无法删除");
        }
    }

    /**
     * 遍历线索化二叉树
     */
    public void threadList() {
        Node node = root;
        while (node != null) {
            //循环查找leftType=1的节点
            while (node.getLeftTyep() == 0) {
                node = node.getLeft();
            }
            //打印当前节点
            System.out.println(node);
            //如果当前节点的右指针，指向的是后置节点
            while (node.getRightType() == 1) {
                //当前节点的右指针是后继节点
                node = node.getRight();
                System.out.println(node);
            }
            //替换遍历的节点
            node = node.getRight();
        }

    }

    /**
     * 前序遍历 线索化二叉树
     */
    public  void threadedListPre(){
        Node node=root;
        while (node!=null){
            //先输出当前节点
            System.out.println(node);
            //循环查找左节点
            while (node.getLeftTyep()==0){
                //一直找到叶子节点
                node=node.getLeft();
            }
            //判断当前指针的右指针是否是后置节点
            while (node.getRightType()==1){
                node=node.getRight();
                System.out.println(node);
            }
            //如果右节点不是
            node=node.getRight();
        }

    }
}

class Node {
    private int id;
    private String name;
    private Node left;
    private Node right;
    //0 表示左子树  1 表示表示指向前驱节点
    private int leftTyep;
    //0 表示右子树  1 表示表示指向后继节点
    private int rightType;

    public Node(int id, String name, int leftTyep, int rightType) {
        this.id = id;
        this.name = name;
        this.leftTyep = leftTyep;
        this.rightType = rightType;
    }

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public int getLeftTyep() {
        return leftTyep;
    }

    public void setLeftTyep(int leftTyep) {
        this.leftTyep = leftTyep;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        System.out.println(this);//先输出父节点
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        //递归向左子树中序遍历
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);//输出当前节点 父节点
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);//输出当前节点 父节点
    }

    /**
     * 前序遍历查找
     *
     * @param no
     * @return
     */
    public Node preSearch(int no) {
        if (this.getId() == no) {
            return this;
        }
        Node resultNode = null;
        if (this.getLeft() != null) {
            resultNode = this.getLeft().preSearch(no);
        }
        if (resultNode != null) {
            return resultNode;
        }
        if (this.getRight() != null) {
            resultNode = this.getRight().preSearch(no);
        }
        return resultNode;
    }

    /**
     * 中序遍历查找
     *
     * @param no
     * @return
     */

    public Node infixSearch(int no) {
        Node resultNode = null;
        if (this.getLeft() != null) {
            resultNode = this.getLeft().infixSearch(no);
        }
        if (resultNode != null) {
            return resultNode;
        }
        if (this.getId() == no) {
            return this;
        }
        if (this.getRight() != null) {
            resultNode = this.getRight().infixSearch(no);
        }
        return resultNode;
    }

    /**
     * 后序遍历
     *
     * @param no
     * @return
     */
    public Node postSearch(int no) {
        Node resultNode = null;
        if (this.getLeft() != null) {
            resultNode = this.getLeft().postSearch(no);
        }
        if (resultNode != null) {
            return resultNode;
        }
        if (this.getRight() != null) {
            resultNode = this.getRight().postSearch(no);
        }
        if (resultNode != null) {
            return resultNode;
        }
        if (this.getId() == no) {
            return this;
        }
        return resultNode;

    }

    /**
     * 删除某个节点
     *
     * @param no
     */
    public void delete(int no) {
        /**
         * 左子树不为空，且正好是删除元素 ，将这个节点的子树都删掉
         */
        if (this.getLeft() != null && this.getLeft().getId() == no) {
            this.setLeft(null);
            return;
        }
        if (this.getRight() != null && this.getRight().getId() == no) {
            this.setRight(null);
            return;
        }
        //向左子树递归删除
        if (this.getLeft() != null) {
            this.getLeft().delete(no);
        }
        //向右子树递归删除
        if (this.getRight() != null) {
            this.getRight().delete(no);
        }

    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", leftTyep=" + leftTyep +
                ", rightType=" + rightType +
                '}';
    }
}
